package tree.tree2.symmetry.Path;

import tree.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName HasAllPathSum
 * @Description TODO
 * @Author lenovo
 * @Date 2023-05-04 11:17
 * @Version 1.0
 * @Comment Magic. Do not touch.
 * If this comment is removed. the program will blow up
 */
public class HasAllPathSum {

    public List<List<Integer>> pathSum1(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();

        depth(res,temp,0,root,targetSum);
        return res;

    }

    private void depth(List<List<Integer>> res, List<Integer> temp, int num, TreeNode root, int targetSum) {
        if (root == null) return;

        num+=root.val;
        temp.add(root.val);

        if(root.left==null && root.right==null && targetSum==num){
            res.add(temp);
        }

        depth(res,new ArrayList<>(temp),num,root.left,targetSum);
        depth(res,new ArrayList<>(temp),num,root.right,targetSum);
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1);
        treeNode.left = new TreeNode(2);
        treeNode.right = new TreeNode(1);
        treeNode.right.right = new TreeNode(1);
        HasAllPathSum hasPathSum = new HasAllPathSum();
        System.out.println(hasPathSum.pathSum1(treeNode, 3));
    }
}